package org.uc3m.ed.tad.arbol;

import java.util.NoSuchElementException;

import org.uc3m.ed.tad.lista.IPila;
import org.uc3m.ed.tad.lista.Pila;





/**
 * Implementacion <B>no robusta</B> de un iterador para arbol binario. El
 * iterador permite recorrer los elementos del arbol en preorden, inorden o
 * postorden segun la decision del usuario.
 * 
 * </br></br>
 * 
 * <B>IMPORTANTE:</B> La implementacion del iterador permite realizar el
 * recorrido de los arboles sin aplanarlos previamente.
 * 
 * @author DEI - ED
 * @version 1.0
 */

public class ArbolBinarioIteradorOptimo<C extends Comparable<C>, E> implements IArbolBinarioIterador<C, E> 
{
	
	
	/**
	 * Pila para realizar el recorrido del arbol sin aplanar previamente su
	 * contenido.
	 * 
	 * @see IPila
	 */
	IPila<IArbolBinario<C,E>> _pila;	
	
	/**
	 * Tipo de recorrido a realizar sobre el arbol.
	 * 
	 */
	Recorrido _recorrido;	

	/**
	 * Crea un iterador sobre un arbol. El arbol se recorre en inorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	public ArbolBinarioIteradorOptimo(IArbolBinario<C, E> arbol) 
	{
		_recorrido=Recorrido.Inorden;
		_pila=new Pila<IArbolBinario<C,E>>();
		iniciarInorden(arbol);
	}

	/**
	 * Crea un iterador sobre un arbol. El arbol respeta el recorrido indicado
	 * por parametro.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 * @param recorrido
	 *            Define el recorrido seguido por el iterador.
	 */
	public ArbolBinarioIteradorOptimo(IArbolBinario<C, E> arbol, Recorrido recorrido) 
	{
		_recorrido=recorrido;
		_pila=new Pila<IArbolBinario<C,E>>();
		switch(_recorrido)
		{
			case Inorden:
				iniciarInorden(arbol);
				break;
			case Postorden:
				iniciarPostorden(arbol);
				break;
			case Preorden:
				iniciarPreorden(arbol);
				break;
		}
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.arbol.ArbolBinarioIterador#haySiguiente()
	 */
	public boolean haySiguiente() 
	{
		return !_pila.estaVacia();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.arbol.ArbolBinarioIterador#siguiente()
	 */
	public E siguiente() 
	{
		E elemento=null;
		if(!haySiguiente())
			throw new NoSuchElementException(); 
		switch(_recorrido)
		{
			case Inorden:
				elemento= siguienteInorden();
				break;
			case Postorden:
				elemento= siguientePostorden();
				break;
			case Preorden:
				elemento=siguientePreorden();
				break;
		}
		 return elemento;
	}
	
	/**
	 * Inicializa el contenido de la pila para realizar el recorrido inorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void iniciarInorden(IArbolBinario<C, E> arbol) 
	{
		IArbolBinario<C, E> auxArbol=arbol.subarbolIzquierdo();
		_pila.anyadir(arbol);
		while (auxArbol!=null)
		{
			_pila.anyadir(auxArbol);
			auxArbol=auxArbol.subarbolIzquierdo();
		}
		
	}

	/**
	 * Inicializa el contenido de la pila para realizar el recorrido preorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void iniciarPreorden(IArbolBinario<C, E> arbol) 
	{
		_pila.anyadir(arbol);
	}

	/**
	 * Inicializa el contenido de la pila para realizar el recorrido postorden.
	 * 
	 * @param arbol
	 *            Arbol sobre la cual se realizara la iteracion.
	 */
	private void iniciarPostorden(IArbolBinario<C, E> arbol) 
	{
		IArbolBinario<C, E> auxArbol=arbol.subarbolIzquierdo();
		_pila.anyadir(arbol);
		while (auxArbol!=null)
		{
			_pila.anyadir(auxArbol);
			auxArbol=auxArbol.subarbolIzquierdo();
		}
	}

	/**
	 * Busca el siguiente elemento del arbol en un recorrido inorden.
	 * 
	 * @return Siguiente elemento.
	 */
	private E siguienteInorden() 
	{
		IArbolBinario<C, E> auxArbol=null;
		IArbolBinario<C, E> arbolSalida = arbolSalida=_pila.extraer();
		auxArbol=arbolSalida.subarbolDerecho();
		if(auxArbol!=null)
		{
			_pila.anyadir(auxArbol);
			auxArbol=auxArbol.subarbolIzquierdo();
			while (auxArbol!=null)
			{
				_pila.anyadir(auxArbol);
				auxArbol=auxArbol.subarbolIzquierdo();
			}			
		}
		return arbolSalida.raiz();
	}

	/**
	 * Busca el siguiente elemento del arbol en un recorrido preorden.
	 * 
	 * @return Siguiente elemento.
	 */	
	private E siguientePreorden() 
	{
		IArbolBinario<C, E> arbolSalida = arbolSalida=_pila.extraer();
		
		if(arbolSalida.subarbolDerecho()!=null)
			_pila.anyadir(arbolSalida.subarbolDerecho());
		if(arbolSalida.subarbolIzquierdo()!=null)
			_pila.anyadir(arbolSalida.subarbolIzquierdo());
		
		return arbolSalida.raiz();
	}

	/**
	 * Busca el siguiente elemento del arbol en un recorrido postorden.
	 * 
	 * @return Siguiente elemento.
	 */	
	private E siguientePostorden() 
	{
		IArbolBinario<C, E> auxArbol=null;
		IArbolBinario<C, E> arbolSalida = arbolSalida=_pila.extraer();
		if(!_pila.estaVacia())
		{
			auxArbol=_pila.extraer();
			_pila.anyadir(auxArbol);
			if(auxArbol.subarbolDerecho()!=null && auxArbol.subarbolDerecho().raiz()!=arbolSalida.raiz())
			{
				auxArbol=auxArbol.subarbolDerecho();
				_pila.anyadir(auxArbol);
				auxArbol=auxArbol.subarbolIzquierdo();
				while (auxArbol!=null)
				{
					_pila.anyadir(auxArbol);
					auxArbol=auxArbol.subarbolIzquierdo();
				}	
			}
		}
		return arbolSalida.raiz();
	}	

}
